# La récursivité en programmation

## Introduction

La répétion d'instructions (cf structures itératives `while` et `for`) est
omniprésente dans la résolution de problèmes algorithmiques.

La récursivité, est une autre forme de structure de contrôle pour traiter
les données, qu'elle permet parfois de résoudre plus intuitivement.


## Concepts clés

### Définition

Une **fonction récursive** est une fonction qui s'appelle elle-même, ce qui déclanche
un cycle (une répétition). La récursivité permet de résoudre un problème en
le réduisant à un ou plusieurs sous-problèmes plus petits de même nature.

Une fonction récursive comprend :

- un (ou plusieurs) **cas de base** / condition(s) d'arrêt : des situation
simples qui pour lesquels il n'y a plus d'appels récursifs ;
- un (ou plusieurs) appel(s) récursif(s) : l'étape qui réduit le problème
vers le cas de base.

```python
def fcn_recursive(…) -> …:
    if condition_arret:
        resultat = cas_de_base
    else:
        resultat = fcn_recursive(…)    #la fonction se rappelle (cycle)
    return resultat
```

Chaque appel a ses propres variables locales et son propre point de reprise.

*Le cas de base est indispensable pour éviter les cycles d'appels infinis.*

### Exemple - factorielle

*La factorielle n'un nombre `n`, notée `n!` est le produit de ce nombre par
tous les nombres supérieurs à 0 qui le précèdent : `n! = n x (n-1) x (n-2) x … x 1` ;
exemple : `4! = 4 x 3 x 2 x 1`.*

La factorielle se résoud sans difficultés avec une structure itérative `for` :

```python
def factorielleIte(n: int) -> int:
    """
    calcule la factorielle d'un nombre
    @param n le nombre dont on veut calculer la factorielle
    @return n!
    précondition : n ≥ 0
    """
    result = 1
    for i in range(2, n+1): #on peut commencer à 2 (0! = 1, et 1 x 1 = 1)
        result = result * i
    return result

print(factorielleIte(4))
```

La factorielle est un exemple emblématique d'une résolution récursive ; en
effet `n! = n x (n-1)!` :

```python
def factorielleRec(n: int, trace: int = 0) -> int:
    print("  " * trace + "factorielleRec(" + str(n) + ") = ", end="")
    if n == 0: #cas de base : 0! = 1
        print("1")
        resultat = 1
    else:
        print(str(n) + " x factorielleRec(" + str(n-1) + ")")
        resultat = n * factorielleRec(n-1, trace + 1)
    return resultat

print(factorielleRec(5))
```

A chaque appel, si la condition d'arrêt du cas de base n'est pas vérifiée,
il y a un appel récursif, dont la fonction appelante *attend* le résultat.

*Remarque : la variable `trace` et les instructions `print` de la fonction
n'ont qu'une finalité pédagogique (pour tracer les appels récursifs).*

Cette fonction est généralement écrite de façon plus compacte :

```python
def factorielleRec(n: int) -> int:
    if n <= 1: #cas de base: 0! = 1! = 1
        return 1
    else:
        return n * factorielleRec(n-1)
```

ou encore plus simplement :

```python
def factorielleRec(n: int) -> int:
    return 1 if n <= 1 else n * factorielleRec(n-1)
```

Cet exemple illustre le remplacement de la structure itérative `for` par une
alternative (cas de base) et un appel récursif.


## Autre exemple - somme des éléments d'un tableau

Algorithme itératif qui effectue la somme des éléments d'un tableau :

```python
from typing import List

def sommeIte(tab: List[float]) -> float:
    total = 0
    for v in tab:
        total += v
    return total
        
print(sommeIte([2, 4, 7, 12]))
```

Et sa version récursive :

```python
from typing import List

def sommeRec(tab: List[float]) -> float:
    if len(tab) == 0:
        return 0
    else:
        return tab[0] + sommeRec(tab[1:]) #tab[1:] copie tab à partir de l'indice 1

print(sommeRec([2, 4, 7, 12]))
```


## Complément : récursion terminale

Lorsque l'appel récursif est la dernière instructions de la fonction (comme c'est
le cas avec la factorielle), la forme de la récursion est dite **terminale**.
S'il y a récursion terminale, l'algorithme récursif peut être converti en
itératif (sans pile) ; c'est ce que font automatiquement certains compilateurs
ou interpréteurs.